Oktálový strom

Oktálový strom, známy aj pod anglickým názvom octree, je údajová štruktúra používaná predovšetkým v počítačovej grafike na efektívnu reprezentáciu voxelových údajov.

Voxely

Jednou z možných reprezentácií trojrozmerných objektov sú tzv. voxely, ktoré sú trojrozmernou analógiou pixelov. Sú to elementárne častice objemu, ktoré možno chápať ako dostatočne malé kocky. Priamočiara voxelová reprezentácia trojrozmerných objektov pomocou trojrozmerného poľa je však značne pamäťovo náročná. Jednou z pamäťovo efektívnejších možností takejto reprezentácie 3D objektov sú oktálové stromy.

Reprezentácia oktálovým stromom

Celú scénu obsahujúcu modelované 3D údaje možno chápať ako kocku. V prípade reprezentácie pomocou voxelov je táto kocka rozdelená na spravidla veľké množstvo menších kociek, ktoré zodpovedajú voxelom. Každý voxel môže nadobúdať binárnu hodnotu 1 alebo 0 podľa toho, či je plný (je súčasťou modelovaného objektu) alebo prázdny (nie je súčasťou modelovaného objektu).

Myšlienka oktálových stromov je, že sa do pamäte neukladajú nutne všetky voxely, ale ak v scéne existuje napr. kocka o 2 x 2 (alebo viac) voxeloch s rovnakou hodnotou všetkých voxelov, uloží sa do pamäte iba informácia o tejto kocke.

Na realizáciu tejto myšlienky sa používa strom, ktorého každý uzol, ktorý nie je listom, má presne osem synov. Koreň stromu zodpovedá celej scéne, každý iný uzol nejakej jej časti (kocke). Každý uzol môže nadobúdať jednu z troch hodnôt, ktoré určujú charakter kocky zodpovedajúcej danému uzlu. Možné hodnoty sú:

plná kocka, obsahuje len plné voxely,
prázdna kocka, obsahuje len prázdne voxely,
heterogénna kocka, obsahuje aj plné aj prázdne voxely.

V prípade, že je v danom uzle uložená jedna z prvých dvoch hodnôt, daný uzol už obsahuje kompletnú informáciu o charaktere zodpovedajúcej kocky, a teda už nemá žiadnych synov. V prípade, že je kocka heterogénna, má daný uzol presne osem synov, ktoré reprezentujú oktanty (osminy) danej kocky. V najhoršom prípade môže takéto delenie na osminy pokračovať až na úroveň voxelov, ale vo väčšine prípadov znamená takýto postup značnú pamäťovú úsporu.

Zdroj

Ružický, E., Ferko, A.: Počítačová grafika a spracovanie obrazu. Bratislava: Sapientia, 1995

Externé odkazy

Implementácia Archivované 2014-11-21 na Wayback Machine oktálového stromu v jazyku C++ (po anglicky)
Octree (po anglicky)